package kibahed.university.effizientealgorithmen.algortihms;

import java.util.ArrayList;

import kibahed.university.effizientealgorithmen.interfaces.AAlgorithm;
import kibahed.university.effizientealgorithmen.interfaces.IEdge;
import kibahed.university.effizientealgorithmen.interfaces.IGraph;
import kibahed.university.effizientealgorithmen.interfaces.IVertex;
import kibahed.university.effizientealgorithmen.standardclasses.EdgeWithCosts;

public class ExhaustiveSearch extends AAlgorithm {

	int[] nodes;
	private ArrayList<int[]> permutations;
	private double shortestTourLength;
	int[] bestTour;
	
	public ExhaustiveSearch(IGraph graph) {
		setGraph(graph);
		prepareNodes();
	}

	private void prepareNodes() {
		nodes = new int[graph.getVertexes().length];
		int i = 0;
		for(IVertex v : graph.getVertexes()) {
			nodes[i] = v.getID();
			i++;
		}
		
	}

	@Override
	public void calculate() {
		prepareNodes();
		createPermutations(nodes);
		evalBestTour();
		convertToEdgeTour(bestTour);
	}

	private void createPermutations(int[] nodes) {
		permutations = new ArrayList<int[]>();
		int[] onePermuation = new int[nodes.length];
		for (int i = 0; i < nodes.length; i++) {
			onePermuation[i] = -1;
		}
		createPermutationsRek(nodes, 0, onePermuation);
	}

	private void createPermutationsRek(int[] nodes, int k, int[] onePermuation) {
		if (k == nodes.length) {
			permutations.add(onePermuation);
		} else {

			for (int i = 0; i < nodes.length; i++) {
				int[] copy = new int[onePermuation.length];
				System.arraycopy(onePermuation, 0, copy, 0,
						onePermuation.length);

				if (onePermuation[i] == -1) {
					copy[i] = nodes[k];
					createPermutationsRek(nodes, k + 1, copy);
				}
			}
		}
	}
	
	private void convertToEdgeTour(int[] nodes) {
		ArrayList<IEdge> tour = new ArrayList<>();
		for(int i = 0; i < nodes.length-1; i++) {
			IEdge e = graph.getEdgeBetweenVertices(nodes[i], nodes[i+1]);
			tour.add(e);
		}
		tour.add(graph.getEdgeBetweenVertices(nodes[0], nodes[nodes.length-1]));
		IEdge[] r = new IEdge[tour.size()];
		setResult(tour.toArray(r));
	}
	
	private void evalBestTour() {
		double min = Double.MAX_VALUE;
		for (int[] tour : permutations) {
			double length = evalLength(tour);
			if (length < min) {
				min = length;
				bestTour = tour;
			}
		}
		shortestTourLength = min;
	}
	
	private double evalLength(int[] tour) {
		double l = 0;
		for(int i = 0; i<tour.length-1; i++) {
			IEdge e = graph.getEdgeBetweenVertices(tour[i], tour[i+1]);
			l += ((EdgeWithCosts)e).getCost();
		}
		IEdge e = graph.getEdgeBetweenVertices(tour[0], tour[tour.length-1]);
		l+= ((EdgeWithCosts)e).getCost();
		return l;
	}
}
